class Solution300_3 {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length ;

        // 状态表示 : 以i结尾的 最长递增子序列长度
        int[] dp = new int[n];
        int max = 0 ;
        dp[0] = 1 ;
        for(int i=1 ; i < n ; i ++){
            // 只有自己
            dp[i] = 1 ;
            for(int j=i-1 ; j >= 0 ; j --){

                // 找[0,i-1]区间里 , 有比 第i个小的
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i] , dp[j] + 1) ;
                }
            }
            max = Math.max(dp[i] , max) ;
        }


        return max ;
    }
}